<?php

/** 
* Title: Double linked list
* Description: Implementation of a double linked list in PHP 
* @author Sameer Borate | http://www.codediesel.com
* Reference : Data Structures & Algorithms in Java : Robert Lafore
* @version 1.0 20th June 2009
*/


class ListNode {
    
    public $id;
	public $data;
    public $next;
    public $previous;

    function __construct($id, $data) {
        $this->id = $id;
		$this->data = $data;
    }

	public function getId() {
		return $this->id;
	}
    public function getData() {
        return $this->data;
    }
	public function setData($data) {
        $this->data = $data;
    }
	public function getNextNode() {
        return $this->next;
    }
	public function getPrevNode() {
        return $this->previous;
    }
}


class DoublyLinkedList {
    
    private $_firstNode;
    private $_lastNode;
    private $_count;

    function __construct() {
        $this->_firstNode = NULL;
        $this->_lastNode = NULL;
        $this->_count = 0;
    }

	public function getFirstNode() {
		return $this->_firstNode;
	}

	public function getLastNode() {
		return $this->_lastNode;
	}

    public function isEmpty() {
        return ($this->_firstNode == NULL);
    }

    public function insertFirst($id, $data) {
        $newLink = new ListNode($id, $data);
        
        if($this->isEmpty()) {
            $this->_lastNode = $newLink;
        } else {
            $this->_firstNode->previous = $newLink;
        }
        
        $newLink->next = $this->_firstNode;
        $this->_firstNode = $newLink;
        $this->_count++;
    }
    
    
    public function insertLast($id, $data) {
        $newLink = new ListNode($id, $data);
        
        if($this->isEmpty()) {
            $this->_firstNode = $newLink;
        } else {
            $this->_lastNode->next = $newLink;
        }
        
        $newLink->previous = $this->_lastNode;
        $this->_lastNode = $newLink;
        $this->_count++;
    }
    
    
    public function insertAfter($id, $data) {
        $current = $this->_firstNode;
        
        while($current->id != $id) {
            $current = $current->next;
            
            if($current == NULL)
                return false;
        }
        
        $newLink = new ListNode($id, $data);
        
        if($current == $this->_lastNode) {
            $newLink->next = NULL;
            $this->_lastNode = $newLink;
        } else {
            $newLink->next = $current->next;
            $current->next->previous = $newLink;
        }
        
        $newLink->previous = $current;
        $current->next = $newLink;
        $this->_count++;
        
        return true;
    }

    
    public function deleteFirstNode() {
        
        $temp = $this->_firstNode;
        
        if($this->_firstNode->next == NULL) {
            $this->_lastNode = NULL;
        } else {
            $this->_firstNode->next->previous = NULL;
        }
        
        $this->_firstNode = $this->_firstNode->next;
        $this->_count--;
        return $temp;
    }


    public function deleteLastNode() {
        
        $temp = $this->_lastNode;
        
        if($this->_firstNode->next == NULL) {
            $this->firtNode = NULL;
        } else {
            $this->_lastNode->previous->next = NULL;
        }
        
        $this->_lastNode = $this->_lastNode->previous;
        $this->_count--;
        return $temp;
    }
    
    
    public function deleteNode($id) {
        
        $current = $this->_firstNode;
        
        while($current->id != $id) {
            $current = $current->next;
            if($current == NULL)
                return null;
        }
        
        if($current == $this->_firstNode) {
            $this->_firstNode = $current->next;
        } else {
            $current->previous->next = $current->next;
        }
        
        if($current == $this->_lastNode) {
            $this->_lastNode = $current->previous;
        } else {
            $current->next->previous = $current->previous;
        }
        
        $this->_count--;
        return $current;
    }



    public function displayForward() {
        
        $current = $this->_firstNode;
        
        while($current != NULL) {
			$temp = $current->getData();
            echo $temp['id']." ";
            $current = $current->next;
        }
    }
    
    
    public function displayBackward() {
        
        $current = $this->_lastNode;
        
        while($current != NULL) {
            echo $current->getData() . " ";
            $current = $current->previous;
        }
    }
    
	
	public function display_node_detail($id) {
		$current = $this->_firstNode;
		while($current != NULL) {
			//$temp = $current->getData();
			if($current->id == $id) {
				$temp_1 = $current->getNextNode();
				$temp_2 = $temp_1->getData();
				echo $temp_2['id'];
			}            
            $current = $current->next;
        }
	}
	
	public function getBestNode() {
		$current = $this->_firstNode;
		$temp = $current->getData();
        $best_value = $temp['f'];
		$best_node = $current;
        while($current != NULL) {
			$temp = $current->getData();
            if($temp['f'] < $best_value) {
				$best_value = $temp['f'];
				$best_node = $current;
			}
            $current = $current->next;
        }
		return $best_node;
	}
	
	public function updateNode($id, $data) {
		$current = $this->_firstNode;
        
        while($current != NULL) {
			if($current->id == $id) {
				$current->setData($data);
				break;
			}
            $current = $current->next;
        }
	}
	
	public function findNode($id) {
		$current = $this->_firstNode;
        
        while($current != NULL) {
			if($current->id == $id) {
				return true;
			}
            $current = $current->next;
        }
		return false;
	}
	
	public function getNode($id) {
		$current = $this->_firstNode;
        
        while($current != NULL) {
			if($current->id == $id) {
				return $current;
			}
            $current = $current->next;
        }
		return NULL;
	}
	
    public function totalNodes() {
        return $this->_count;
    }

}
?>